﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/special-array-with-x-elements-greater-than-or-equal-x/
/*
题目描述：
给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，
那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，
如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
 
示例 1：
输入：nums = [3,5]
输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。

示例 2：
输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。

示例 3：
输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。

示例 4：
输入：nums = [3,6,7,7,0]
输出：-1

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000
*/

// 方法1——暴力法
/*
思路：
枚举x从1到numsSize的所有数字，对于每个数字都遍历数组nums，
统计数组中大于或等于x的数字，用一个变量count统计，如果最后count == x则返回x。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int specialArray1(int* nums, int numsSize) {
	assert(nums);
	int i = 0;
	int j = 0;
	int count = 0;
	for (i = 1; i <= numsSize; i++) {
		count = 0;
		for (j = 0; j < numsSize; j++) {
			if (nums[j] >= i) {
				count++;
			}
		}
		if (count == i) {
			return i;
		}
	}
	return -1;
}
// 时间复杂度：O(n^2)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——排序后二分
/*
思路：
当对数组进行排序制后，我们可以使用二分法找到第一个大于等于x的元素，
再判断从该元素到末尾的元素个数是否刚好等于x，如果等于，则返回x。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整型的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
int specialArray2(int* nums, int numsSize) {
	assert(nums);
	// 先对数组进行排序
	qsort(nums, numsSize, sizeof(int), cmp_int);
	int x = 0;
	int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	for (x = 1; x <= numsSize; x++) {
		left = 0;
		right = numsSize - 1;
		while (left < right) {
			if (nums[left] >= x) {
				break;
			}
			mid = left + (right - left) / 2;
			if (nums[mid] < x) {
				left = mid + 1;
			}
			else {
				right = mid;
			}
		}
		if (nums[left] >= x) {
			if (numsSize - left == x) {
				return x;
			}
		}
	}
	return -1;
}
// 时间复杂度：O(nlogn)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法3——降序排序
/*
思路：
当我们对数组进行降序排序制后，nums[i]之前的元素，一定是大于nums[i]的，
而又因为数组的下标时从0开始的，所以我们如果找到一个元素满足nums[i] < i && nums[i - 1] >= i
那就说明数组中恰好有(i - 1) +1 = i个元素大于等于i，所以i就是我们要求的特征值，直接返回i即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，反向比较两个整型的大小
int cmp_int2(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p2) - *((int*)p1);
}
int specialArray3(int* nums, int numsSize) {
	assert(nums);
	// 先对数组进行降序排序
	qsort(nums, numsSize, sizeof(int), cmp_int2);
	// 特殊的
	if (nums[numsSize - 1] >= numsSize) {
		return numsSize;
	}
	int i = 0;
	for (i = 0; i < numsSize; i++) {
		if (nums[i] < i && nums[i - 1] >= i) {
			return i;
		}
	}
	return -1;
}
// 时间复杂度：O(nlogn)，排序数组的复杂度为nlogn，遍历数组的复杂度为n，故总体时间复杂度为：O(nlogn)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

int main() {
	int nums[] = { 1,0,0,6,4,9 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);
	int result = specialArray2(nums, numsSize);
	printf("%d\n", result);
	return 0;
}

